package leetcode_jz_offer.day9;

/**
 * @author 美女
 * @date 2022/07/17 14:47
 **/
public class Num42_连续子数组最大和 {
    //dp[i]：以i结尾的数组元素的最大和
    //连续子数组最大和max(dp[i])=getMax(max(dp[i-1]+arr[i],arr[i]))
    /** 解释：数组元素最大和可以有两种//两种求法：1）dp[i-1]+nums[i]；2)nums[i]，1）是将i-1的最大和和当前的值相加，得到值，2）是应用当前值本身。当当前值和i-1对应的值加起来比当前值高，则选择1)，当加起来小于当前值，则当前值就是最大值*/
    public int maxSubArray(int[] nums) {
        //初始化
        int sum=nums[0];//当前连续子数组的最大和,直接将第一个元素值放入
        int max=nums[0];//连续子数组最大和
        for(int i=1;i<nums.length;i++){
            sum=Math.max(nums[i]+sum,nums[i]);//将dp[i-1]+nums[i]与nums[i]的最大值给dp[i]
            max=max>sum?max:sum;
        }
        return max;
    }
}
